
//1514.概率最大的路径
class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start_node, int end_node) {
        //此题不过是将找最短路径改变成了找最大概念而已
        vector<vector<pair<int,double>>> path(n);       //记录每条路的情况和成功概率
        //1. 先统计每条路的情况
        for(int i = 0;i < edges.size() ;i++)
        {
            int x = edges[i][0] , y = edges[i][1];
            double prob = succProb[i];

            path[x].emplace_back(y,prob);
            path[y].emplace_back(x,prob);
        }

        //2. 开始准备遍历
        vector<int> vist(n);                       //记录以及作为起始位置的数字
        vector<double>  dis(n,0);                 //记录到达每个位置的概率
        priority_queue<pair<double,int>> pq;       //此时就需要使用大堆了,因为要从概率大的位置开始
        pq.push({1,start_node});
        vist[start_node] = 1;

        while(pq.size())
        {
            auto [prob,pos]  = pq.top();;
            pq.pop();
            if(dis[pos] >= prob) continue;
            dis[pos] = prob;
            vist[pos] = 1;

            for(auto& [next,t] : path[pos])
                if(t*prob > dis[next] && !vist[next]) pq.push({t*prob,next});
        }
        return dis[end_node] ;
    }
};